// Created by WXX on 2021/11/29 22:07
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：784 ms, 在所有 C++ 提交中击败了14.02%的用户
 * 内存消耗：413.8 MB, 在所有 C++ 提交中击败了9.36%的用户
 */
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {

        int n = nums.size();
        vector<vector<int>> f(n, vector<int>(20010));  // f[i][j]: 以i结尾公差为j的子序列长度最大值

        int res = 2;
        for (int i = 0; i < n; i++)
            for (int k = 0; k < i; k++) {  // 枚举前一个数
                // 公差可以算出来
                int j = nums[i] - nums[k] + 10000;
                f[i][j] = max(f[i][j], 2);
                f[i][j] = max(f[i][j], f[k][j] + 1);
                res = max(res, f[i][j]);
            }
        return res;
    }
};

int main() {

    vector<int> nums = {3, 6, 9, 12};
    cout << Solution().longestArithSeqLength(nums) << endl;  // 4

    return 0;
}
